πŸ’‘ Graph 이둠

@Seongukbaek Posted December 28, 2021 Β· Updated December 28, 2021 Β· 22 min read

πŸ“– κ·Έλž˜ν”„

계측적인 ꡬ쑰보닀 μ’€ 더 일반적이고 κ°•λ ₯ν•œ 자료 ꡬ쑰, μ‚¬λ¬Όμ΄λ‚˜ κ°œλ… κ°„μ˜ μ—°κ²° ꡬ쑰 ex. μ—¬λŸ¬ λ„μ‹œλ“€μ„ μ—°κ²°ν•˜λŠ” λ„λ‘œλ§, μ‚¬λžŒλ“€ κ°„μ˜ 지인 관계, μ›Ή μ‚¬μ΄νŠΈ κ°„μ˜ 링크

νŠΈλ¦¬μ— μžˆμ—ˆλ˜ λΆ€λͺ¨ μžμ‹ 관계에 λŒ€ν•œ μ œμ•½μ΄ μ—†μ–΄ μ’€ 더 λ‹€μ–‘ν•˜κ³  자유둜운 ꡬ쑰 ν‘œν˜„μ΄ κ°€λŠ₯ν•˜λ‹€.


πŸ’‘ μ •μ˜

κ·Έλž˜ν”„ G(V, E)λŠ” μ–΄λ–€ μžλ£Œλ‚˜ κ°œλ…μ„ ν‘œν˜„ν•˜λŠ” 정점(vertex)λ“€μ˜ μ§‘ν•© V와 이듀을 μ—°κ²°ν•˜λŠ” κ°„μ„ (edge)λ“€μ˜ μ§‘ν•© E둜 κ΅¬μ„±λœ 자료 ꡬ쑰

  • μ •μ μ˜ μœ„μΉ˜ μ •λ³΄λ‚˜ κ°„μ„ μ˜ μˆœμ„œ 등은 κ·Έλž˜ν”„μ˜ μ •μ˜μ— ν¬ν•¨λ˜μ§€ μ•ŠλŠ”λ‹€.

πŸ’‘ μ’…λ₯˜

ν‘œν˜„ν•˜κ³ μž ν•˜λŠ” λŒ€μƒμ— 따라 μ—¬λŸ¬ κ°€μ§€ λ³€ν˜•λœ ν˜•νƒœλ₯Ό κ°€μ§ˆ 수 μžˆλ‹€.

λ°©ν–₯ κ·Έλž˜ν”„(directed graph) or 유ν–₯ κ·Έλž˜ν”„

각 간선이 β€œλ°©ν–₯” μ΄λΌλŠ” μƒˆλ‘œμš΄ 속성을 κ°€μ§„λ‹€. 즉, λ°©ν–₯에 따라 μƒˆλ‘œμš΄ κ°„μ„ μœΌλ‘œ λΆ„λ₯˜λœλ‹€. ex. μ‚¬λžŒλ“€ κ°„μ˜ μ§μ‚¬λž‘ 관계, λ„λ‘œμ—μ„œμ˜ 일방 톡행 λ“±

무ν–₯ κ·Έλž˜ν”„(undirected graph) 간선에 λ°©ν–₯이 μ—†λŠ” κ·Έλž˜ν”„

κ°€μ€‘μΉ˜ κ·Έλž˜ν”„(weighted graph)

각 간선에 β€œκ°€μ€‘μΉ˜β€ λΌλŠ” μ‹€μˆ˜ 속성이 μΆ”κ°€λœλ‹€. ex. 두 λ„μ‹œ μ‚¬μ΄μ˜ 거리, 두 물건 μ‚¬μ΄μ˜ κ΅ν™˜ λΉ„μœ¨ λ“±

μ΅œμ†Œ μŠ€νŒ¨λ‹ νŠΈλ¦¬μ™€ μ΅œλ‹¨ 경둜 λ¬Έμ œμ—μ„œ μ€‘μš”ν•œ κ°œλ…μœΌλ‘œ μ‚¬μš©λœλ‹€!

닀쀑 κ·Έλž˜ν”„(multigraph)

두 정점 사이에 두 개 μ΄μƒμ˜ 간선이 μžˆμ„ 수 μžˆλŠ” κ·Έλž˜ν”„

λ‹¨μˆœ κ·Έλž˜ν”„(simple graph)

두 정점 사이에 μ΅œλŒ€ ν•œ 개의 κ°„μ„ λ§Œ μžˆλŠ” κ·Έλž˜ν”„

πŸ“ 트리 or 루트 μ—†λŠ” 트리(unrooted tree)λŠ” λΆ€λͺ¨ μžμ‹ 관계가 없을 뿐, κ°„μ„ λ“€μ˜ μ—°κ²° κ΄€κ³„λ§Œμ„ 보면 무ν–₯ κ·Έλž˜ν”„μ΄λ‹€. 즉, 간선을 톡해 두 정점을 μž‡λŠ” 방법이 λ”± ν•˜λ‚˜λΏμž„μ„ μ˜λ―Έν•œλ‹€.

이뢄 κ·Έλž˜ν”„(bipartite graph)

κ·Έλž˜ν”„μ˜ 정점듀을 κ²ΉμΉ˜μ§€ μ•ŠλŠ” 두 개의 그룹으둜 λ‚˜λˆ μ„œ μ„œλ‘œ λ‹€λ₯Έ 그룹에 μ†ν•œ 정점듀 κ°„μ—λ§Œ 간선이 μ‘΄μž¬ν•˜λ„λ‘ λ§Œλ“€ 수 μžˆλŠ” κ·Έλž˜ν”„ ex. ν•˜νŠΈ μ‹œκ·Έλ„κ³Ό 같은 ν”„λ‘œκ·Έλž¨μ—μ„œμ˜ μ‚¬λž‘μ˜ μž‘λŒ€κΈ°

  • 같은 그룹의 정점듀 κ°„μ—λŠ” 간선이 μ—†λ‹€.

사이클 μ—†λŠ” λ°©ν–₯ κ·Έλž˜ν”„(directed acyclic graph) = DAG

ν•œ μ μ—μ„œ μΆœλ°œν•΄ λ‹€μ‹œ 자기 μžμ‹ μœΌλ‘œ λŒμ•„μ˜€λŠ” κ²½λ‘œκ°€ μ—†λŠ”, 즉 cycle이 μ—†λŠ” λ°©ν–₯ κ·Έλž˜ν”„ ex. μ—¬λŸ¬ μž‘μ—…λ“€ κ°„μ˜ μƒν˜Έ 의쑴 관계

  • κ°„μ„ μ˜ λ°©ν–₯을 λ¬΄μ‹œν•  경우 cycle이 μ‘΄μž¬ν•  μˆ˜λ„ μžˆλ‹€.

πŸ’‘ 경둜

끝과 끝이 μ„œλ‘œ μ—°κ²°λœ 간선듀을 μˆœμ„œλŒ€λ‘œ λ‚˜μ—΄ν•œ 것

λ‹¨μˆœ 경둜

경둜 쀑 ν•œ 정점을 μ΅œλŒ€ ν•œ 번만 μ§€λ‚˜λŠ” 경둜

사이클(cycle)

μ‹œμž‘ν•œ μ μ—μ„œ λλ‚˜λŠ” 경둜


πŸ’‘ ν‘œν˜„ 방법

μ—¬λŸ¬ 객체듀이 μ„œλ‘œ μ—°κ²°λ˜μ–΄ μžˆλ‹€λŠ” 점은 νŠΈλ¦¬μ™€ 큰 차이가 μ—†λ‹€.

  • 각 정점을 객체둜 ν‘œν˜„
  • 각 객체가 μžμ‹ κ³Ό κ°„μ„ μœΌλ‘œ μ—°κ²°λœ 정점듀에 λŒ€ν•œ μ •λ³΄μ˜ λͺ©λ‘μ„ μ €μž₯

λŒ€λ‹€μˆ˜μ˜ 경우, κ·Έλž˜ν”„λŠ” νŠΈλ¦¬μ— λΉ„ν•΄ 훨씬 정적인 μš©λ„λ‘œ μ‚¬μš©λœλ‹€.

  • μƒˆλ‘œμš΄ μ •μ μ΄λ‚˜ 간선을 μΆ”κ°€ν•˜κ³  μ‚­μ œν•˜λŠ” 일이 자주 μΌμ–΄λ‚˜μ§€ μ•ŠλŠ”λ‹€λŠ” 의미
  • λ”°λΌμ„œ, ꡬ쑰의 변경이 어렡더라도 μ’€ 더 κ°„λ‹¨ν•˜κ³  λ©”λͺ¨λ¦¬λ₯Ό 적게 μ°¨μ§€ν•˜λŠ” λ°©λ²•μœΌλ‘œ κ΅¬ν˜„ν•œλ‹€.

κ°„λ‹¨ν•œ 방법

  1. κ·Έλž˜ν”„μ˜ 정점듀을 객체의 instance둜 ν‘œν˜„ν•˜λŠ” λŒ€μ‹  각 정점에 0λΆ€ν„° μ‹œμž‘ν•˜λŠ” 번호λ₯Ό 뢙이고,
  2. 배열에 각 μ •μ μ˜ 정보λ₯Ό μ €μž₯
  3. 간선은 λ°˜λŒ€μͺ½ μ •μ μ˜ 번호λ₯Ό μ €μž₯ν•˜λŠ” λ°©μ‹μœΌλ‘œ κ΅¬ν˜„

인접 리슀트

κ·Έλž˜ν”„μ˜ 각 μ •μ λ§ˆλ‹€ ν•΄λ‹Ή μ •μ μ—μ„œ λ‚˜κ°€λŠ” 간선이 λͺ©λ‘μ„ μ €μž₯ν•˜λŠ” 방식 β†’ κ·Έλž˜ν”„λŠ” 각 μ •μ λ§ˆλ‹€ ν•˜λ‚˜μ˜ μ—°κ²° 리슀트λ₯Ό κ°–λŠ” λ°©μ‹μœΌλ‘œ κ΅¬ν˜„

Java β‡’ List 내뢀에 동적 Listλ₯Ό μ„ μ–Έν•˜μ—¬ μ²˜λ¦¬ν•˜κ³  ν•΄λ‹Ή node와 costλ₯Ό List처럼 μ²˜λ¦¬ν•˜λŠ” κ²½μš°κ°€ 많기 λ•Œλ¬Έμ—, 이λ₯Ό κ΄€λ¦¬ν•˜κΈ° μœ„ν•œ Classλ₯Ό μ„ μ–Έν•˜μ—¬ μ‚¬μš©ν•œλ‹€.

class Node { int node; int cost; Node (int node, int cost) { this.node = node; this.cost = cost; } }

단점 두 정점이 μ£Όμ–΄μ§ˆ λ•Œ 이 정점이 μ—°κ²°λ˜μ–΄ μžˆλŠ”μ§€λ₯Ό μ•ŒκΈ° μœ„ν•΄μ„œλŠ” λͺ¨λ“  μ—°κ²° 리슀트λ₯Ό 일일이 탐색해야 ν•œλ‹€λŠ” 것 β†’ 이와 같은 연산속도λ₯Ό 높이기 μœ„ν•΄ 인접 ν–‰λ ¬ (adjacency matrix) ν‘œν˜„ 방식을 μ‚¬μš©

인접 ν–‰λ ¬

2차원 배열을 μ΄μš©ν•΄ κ·Έλž˜ν”„μ˜ κ°„μ„  정보λ₯Ό μ €μž₯ ex. 1 β†’ 2 β‡’ graph[1][2] = true or cost β†’ κ°€μž₯ κ°„λ‹¨ν•œ ν˜•νƒœμ˜ 경우, 2차원 boolean κ°’ λ°°μ—΄

두 λ°©μ‹μ˜ 비ꡐ

두 방식은 μ •λ°˜λŒ€μ˜ νŠΉμ§•μ„ κ°€μ Έ, μ„œλ‘œμ˜ 단점이 μ„œλ‘œμ˜ μž₯점이 λœλ‹€. λ©”λͺ¨λ¦¬ 곡간 μΈ‘λ©΄κ³Ό 탐색 μ‹œκ°„ 츑면으둜 λ‚˜λ‰œλ‹€.

인접 리슀트의 μž₯점

  • |V| 개의 μ—°κ²° λ¦¬μŠ€νŠΈμ— μ‹€μ œ κ°„μ„  수만큼의 μ›μ†Œλ§Œ μ‘΄μž¬ν•˜κΈ°μ— O(|V|+|E|) 크기의 κ³΅κ°„λ§Œ μ‚¬μš©ν•œλ‹€.

    인접 리슀트의 단점

  • μ •μ μ˜ λ²ˆν˜Έκ°€ μ£Όμ–΄μ§„ 경우, 두 정점을 μž‡λŠ” κ°„μ„ μ˜ 쑴재λ₯Ό μ•ŒκΈ° μœ„ν•΄μ„œλŠ” λͺ¨λ“  μ—°κ²° 리슀트λ₯Ό 탐색해야 ν•œλ‹€.

    인접 ν–‰λ ¬μ˜ μž₯점

  • μ •μ μ˜ λ²ˆν˜Έκ°€ μ£Όμ–΄μ§„ 경우, 두 정점을 μž‡λŠ” κ°„μ„ μ˜ 쑴재λ₯Ό ν•œ 번의 λ°°μ—΄ μ ‘κ·Όλ§ŒμœΌλ‘œ μ•Œ 수 μžˆλ‹€.

    인접 ν–‰λ ¬μ˜ 단점

  • 항상 정점 μ§‘ν•© 전체λ₯Ό μ €μž₯ν•˜κΈ° μœ„ν•œ 2차원 배열을 μ‚¬μš©ν•˜κΈ° λ•Œλ¬Έμ—, 항상 O(|V|^2) 크기의 곡간을 μ‚¬μš©ν•΄μ•Ό ν•œλ‹€.

κ°„μ„ μ˜ μˆ˜κ°€ |V|^2에 λΉ„ν•΄ 훨씬 적은 κ·Έλž˜ν”„: ν¬μ†Œ κ·Έλž˜ν”„(sparse graph) β‡’ 인접 리슀트 κ°„μ„ μ˜ μˆ˜κ°€ |V|^2에 거의 λΉ„λ‘€ν•˜λŠ” κ·Έλž˜ν”„: λ°€μ§‘ κ·Έλž˜ν”„(dense graph) β‡’ 인접 ν–‰λ ¬


πŸ“– 깊이 μš°μ„  탐색 (DFS)

κ·Έλž˜ν”„μ˜ λͺ¨λ“  정점을 λ°œκ²¬ν•˜λŠ” κ°€μž₯ λ‹¨μˆœν•˜κ³  고전적인 λ°©λ²•μœΌλ‘œ, ν˜„μž¬ μ •μ μ—μ„œ λ‹€μŒ κ°€μ§€λ‘œ λ„˜μ–΄κ°€κΈ° 전에, ν•΄λ‹Ή κ°€μ§€λ₯Ό λͺ¨λ‘ νƒμƒ‰ν•˜λŠ” 방법이닀.

  1. ν˜„μž¬ 정점과 μΈμ ‘ν•œ 간선듀을 ν•˜λ‚˜μ”© 검사
  2. 아직 λ°©λ¬Έν•˜μ§€ μ•Šμ€ μ •μ μœΌλ‘œ ν–₯ν•˜λŠ” 간선이 μžˆλ‹€λ©΄ κ·Έ 간선을 탐색
  3. 더 이상 갈 곳이 μ—†λŠ” 경우, λ§ˆμ§€λ§‰μ— λ”°λΌμ™”λ˜ 간선을 따라 λ’€λ‘œ λŒμ•„κ°

DFSμ—μ„œ κ°€μž₯ μ€‘μš”ν•œ νŠΉμ§•μ€ 3λ²ˆμ΄λ‹€. 이λ₯Ό μœ„ν•΄μ„œ μ§€κΈˆκΉŒμ§€ 거쳐온 정점듀을 μ €μž₯ν•΄μ•Ό ν•˜λŠ”λ°, μž¬κ·€ ν˜ΈμΆœμ„ μ΄μš©ν•˜μ—¬ κ°„λ‹¨ν•˜κ²Œ κ΅¬ν˜„ν•  수 μžˆλ‹€.

μ£Όμ˜ν•  점 κ·Έλž˜ν”„μ˜ λͺ¨λ“  정점듀이 κ°„μ„ μœΌλ‘œ μ—°κ²°λ˜μ§€ μ•Šμ€ κ²½μš°κ°€ μžˆμ„ 수 μžˆλ‹€. μ΄λ•Œλ„ λͺ¨λ“  정점듀을 λ³Ό 수 μžˆλŠ” μ½”λ“œλ₯Ό μž‘μ„±ν•  수 μžˆμ–΄μ•Ό ν•œλ‹€.

πŸ’‘ μ‹œκ°„ λ³΅μž‘λ„

인접 리슀트λ₯Ό μ‚¬μš©ν•˜λŠ” 경우

  • ν•œ μ •μ λ§ˆλ‹€ DFS() λŠ” ν•œ λ²ˆμ”© 호좜 β†’ |V| 번
  • O(|V| + |E|)

인접 행렬을 μ‚¬μš©ν•˜λŠ” 경우

  • DFS() 의 ν˜ΈμΆœνšŸμˆ˜λŠ” 인접 λ¦¬μŠ€νŠΈμ™€ λ™μΌν•˜κ²Œ |V| 번
  • λ‹€λ₯Έ λͺ¨λ“  정점을 μˆœνšŒν•˜λ©° 두 정점 사이에 간선이 μžˆλŠ”κ°€λ₯Ό ν™•μΈν•˜λ―€λ‘œ ν•œ λ²ˆμ— O(|V|) μ‹œκ°„μ΄ μ†Œλͺ¨
  • O(|V|^2)

πŸ’‘ μœ„μƒ μ •λ ¬

μ˜μ‘΄μ„±μ΄ μžˆλŠ” μž‘μ—…λ“€μ΄ μ£Όμ–΄μ§ˆ λ•Œ, 이듀을 μ–΄λ–€ μˆœμ„œλ‘œ μˆ˜ν–‰ν•΄μ•Ό ν•˜λŠ”μ§€ 계산

μ˜μ‘΄μ„± κ·Έλž˜ν”„(dependency graph) 각 μž‘μ—…μ„ μ •μ μœΌλ‘œ ν‘œν˜„ν•˜κ³ , μž‘μ—… κ°„μ˜ 의쑴 관계λ₯Ό κ°„μ„ μœΌλ‘œ ν‘œν˜„ν•œ λ°©ν–₯ κ·Έλž˜ν”„ β†’ cycle이 μ—†λŠ” λ°©ν–₯ κ·Έλž˜ν”„, 즉 DAG

μœ„μƒ μ •λ ¬

μ˜μ‘΄μ„± κ·Έλž˜ν”„μ˜ λͺ¨λ“  μ˜μ‘΄μ„±μ΄ 만쑱되렀면, λͺ¨λ“  간선이 μ™Όμͺ½μ—μ„œ 였λ₯Έμͺ½μœΌλ‘œ κ°€μ•Ό ν•˜λŠ”λ°, 이λ₯Ό μœ„ν•΄ DAG의 정점을 λ°°μ—΄ν•˜λŠ” 문제

직관적인 방법

  • λ“€μ–΄μ˜€λŠ” 간선이 ν•˜λ‚˜λ„ μ—†λŠ” 정점을 탐색
  • μ •λ ¬ 결과에 이어 뢙이기
  • κ·Έλž˜ν”„μ—μ„œ ν•΄λ‹Ή 정점을 μ‚­μ œ μœ„ 과정을 반볡

이λ₯Ό DFS λ₯Ό μ΄μš©ν•΄ ν•΄κ²°ν•  수 μžˆλ‹€.

  • ν•œ 정점에 λŒ€ν•œ DFS() κ°€ μ’…λ£Œλ  λ•Œλ§ˆλ‹€ ν˜„μž¬ μ •μ μ˜ 번호λ₯Ό 기둝
  • λͺ¨λ“  탐색이 λλ‚œ ν›„, 정점 λ²ˆν˜Έλ“€μ„ λ’€μ§‘μœΌλ©΄ μœ„μƒ μ •λ ¬ κ²°κ³Ό

πŸ’‘ 이둠적 λ°°κ²½κ³Ό μ‘μš©

깊이 μš°μ„  탐색과 κ°„μ„ μ˜ λΆ„λ₯˜

깊이 μš°μ„  탐색을 μˆ˜ν–‰ν•˜λ©΄ κ·Έ κ³Όμ •μ—μ„œ κ·Έλž˜ν”„μ˜ λͺ¨λ“  간선을 ν•œ λ²ˆμ”©μ€ λ§Œλ‚˜κ²Œ λ˜λŠ”λ°, 일뢀 κ°„μ„ λ§Œμ΄ 처음 λ°œκ²¬ν•œ 정점과 μ—°κ²°λ˜μ–΄ μžˆκΈ°μ— 이λ₯Ό λ”°λΌκ°€κ²Œ λœλ‹€. ! ν•˜μ§€λ§Œ μ—¬κΈ°μ„œ, λ¬΄μ‹œλ˜λŠ” 간선듀을 톡해 κ·Έλž˜ν”„μ˜ ꡬ쑰에 λŒ€ν•œ 정보λ₯Ό μ•Œ 수 μžˆλ‹€.

μ–΄λ– ν•œ κ·Έλž˜ν”„μ— λŒ€ν•œ 깊이 μš°μ„  탐색 μ‹œ, 탐색이 λ”°λΌκ°€λŠ” 일뢀 κ°„μ„ λ“€λ§Œ λͺ¨μ•„보면 β€œνŠΈλ¦¬β€ ν˜•νƒœλ₯Ό λ„κ²Œ λœλ‹€. β†’ 이와 같이 μ–»μ–΄μ§„ 트리λ₯Ό 깊이 μš°μ„  탐색 μŠ€νŒ¨λ‹ 트리 ν˜Ήμ€ DFS μŠ€νŒ¨λ‹ 트리 라고 ν•œλ‹€.

κ°„μ„ μ˜ λΆ„λ₯˜

  • 트리 κ°„μ„ (tree edge) : μŠ€νŒ¨λ‹ νŠΈλ¦¬μ— ν¬ν•¨λœ κ°„μ„ 
  • 순방ν–₯ κ°„μ„ (forward edge) : μŠ€νŒ¨λ‹ 트리의 μ„ μ‘°μ—μ„œ μžμ†μœΌλ‘œ μ—°κ²°λ˜μ—ˆμ§€λ§Œ 트리 간선이 μ•„λ‹Œ κ°„μ„ 
  • μ—­λ°©ν–₯ κ°„μ„ (back edge) : μŠ€νŒ¨λ‹ 트리의 μžμ†μ—μ„œ μ„ μ‘°λ‘œ μ—°κ²°λ˜λŠ” κ°„μ„ 
  • ꡐ차 κ°„μ„ (cross edge) : μœ„μ˜ μ„Έ 간선이 μ•„λ‹Œ κ°„μ„ , 선쑰와 μžμ† 관계가 μ•„λ‹Œ 정점듀 κ°„ μ—°κ²°λœ κ°„μ„ 

μ–΄λ– ν•œ μˆœμ„œλ‘œ 정점을 λ°©λ¬Έν•˜λŠλƒμ— 따라 μ„œλ‘œ λ‹€λ₯Έ νŠΈλ¦¬κ°€ 될 μˆ˜λ„ 있고, 간선에 λŒ€ν•œ λΆ„λ₯˜κ°€ λ‹¬λΌμ§ˆ μˆ˜λ„ μžˆλ‹€.

무ν–₯ κ·Έλž˜ν”„ κ°„μ„ μ˜ λΆ„λ₯˜ 무ν–₯ κ·Έλž˜ν”„μ˜ λͺ¨λ“  간선은 μ–‘λ°©ν–₯으둜 톡행 κ°€λŠ₯ν•˜κΈ° λ•Œλ¬Έμ— ꡐ차 간선이 μžˆμ„ 수 μ—†λ‹€. λ˜ν•œ, 순방ν–₯ κ°„μ„ κ³Ό μ—­λ°©ν–₯ κ°„μ„ μ˜ ꡬ뢄도 μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ”λ‹€.

사이클 쑴재 μ—¬λΆ€ 확인 κ°„μ„  ꡬ뢄을 μ΄μš©ν•˜μ—¬ λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ 사이클이 μ‘΄μž¬ν•˜λŠ”μ§€ μ—¬λΆ€λ₯Ό νŒλ‹¨ν•  수 μžˆλ‹€. β†’ μ—­λ°©ν–₯ κ°„μ„ μ˜ 쑴재 여뢀와 λ™μΌν•œ 문제

간선을 κ΅¬λΆ„ν•˜λŠ” 방법

κ°€μž₯ κ΅¬λΆ„ν•˜κΈ° μ‰¬μš΄ 간선은 트리 간선이닀. κ°„μ„  (u, v)λ₯Ό κ²€μ‚¬ν–ˆμ„ λ•Œ, vκ°€ 방문된 적이 μ—†λ‹€λ©΄ μ΄λŠ” β€œνŠΈλ¦¬ 간선”이 λœλ‹€. ν•˜μ§€λ§Œ vκ°€ 방문된 μ΄ν›„μ˜€λ‹€λ©΄, λΆ€λͺ¨μΈμ§€ μžμ†μΈμ§€ μ•Œ 수 μžˆλŠ” 방법이 μ—†λ‹€. κ·Έλž˜μ„œ 좔가적인 정보λ₯Ό μ €μž₯ν•˜κ³  이λ₯Ό 톡해 λΆ€λͺ¨ μžμ† 관계λ₯Ό νŒŒμ•…ν•  수 μžˆμ–΄μ•Ό ν•œλ‹€.

  • 각 정점을 λ°©λ¬Έν•  λ•Œ, 이 정점이 λ°©λ¬Έλ˜μ—ˆλ‹€λŠ” 사싀 = visited
  • 이 정점이 λͺ‡λ²ˆμ§Έλ‘œ λ°œκ²¬λ˜μ—ˆλŠ”μ§€ = discovered

κ°„μ„  (u, v)μ—μ„œ u와 v의 λ°©λ¬Έ μˆœμ„œ

  • 순방ν–₯ 간선이라면, vλŠ” u의 μžμ†μ΄μ–΄μ•Ό ν•œλ‹€.
  • μ—­λ°©ν–₯ 간선이라면, vλŠ” u의 μ„ μ‘°μ—¬μ•Ό ν•œλ‹€.
  • ꡐ차 간선이라면, dfs(v)κ°€ μ’…λ£Œν•œ ν›„ dfs(u)κ°€ ν˜ΈμΆœλ˜μ–΄μ•Ό ν•œλ‹€.

μœ„ 경우 쀑, 발견 μˆœμ„œ 정보λ₯Ό ν† λŒ€λ‘œ 순방ν–₯ 간선에 λŒ€ν•œ ꡬ뢄은 κ°€λŠ₯ν•˜μ§€λ§Œ, μ—­λ°©ν–₯ κ°„μ„ κ³Ό ꡐ차 간선에 λŒ€ν•œ ꡬ뢄은 μ—¬μ „νžˆ λΆˆκ°€λŠ₯ν•˜λ‹€. κ·Έλž˜μ„œ, dfs(v)의 μ’…λ£Œ μ—¬λΆ€ λ˜ν•œ 확인해주어야 ν•œλ‹€.


πŸ“– λ„ˆλΉ„ μš°μ„  탐색 (BFS)

깊이 μš°μ„  탐색과 ν•¨κ»˜ κ°€μž₯ 널리 μ‚¬μš©λ˜λŠ” κ·Έλž˜ν”„ 탐색 μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, "λ‹€μ΅μŠ€νŠΈλΌμ˜ μ΅œλ‹¨ 거리 μ•Œκ³ λ¦¬μ¦˜"μ΄λ‚˜ "ν”„λ¦Όμ˜ μ΅œμ†Œ μŠ€νŒ¨λ‹ 트리 μ•Œκ³ λ¦¬μ¦˜" 등에 μ‚¬μš©λœλ‹€.

β€μ‹œμž‘μ μ—μ„œ μ΅œμ†Œ 거리 κΈ°μ€€μœΌλ‘œ κ°€κΉŒμš΄ 정점뢀터 μˆœμ„œλŒ€λ‘œ λ°©λ¬Έν•˜λŠ” 탐색 μ•Œκ³ λ¦¬μ¦˜β€μœΌλ‘œ, μ΅œμ†Œ λΉ„μš©μ„ ꡬ할 λ•Œ μ ν•©ν•˜λ‹€.

  1. 각 정점을 λ°©λ¬Έν•  λ•Œλ§ˆλ‹€ λͺ¨λ“  인접 정점듀을 검사
  2. 이 쀑 처음 λ³΄λŠ” 정점을 λ°œκ²¬ν•˜λ©΄ λ°©λ¬Έ μ˜ˆμ •μ΄λΌκ³  κΈ°λ‘ν•˜κ³  λ³„λ„μ˜ μœ„μΉ˜μ— μ €μž₯(Queue)
  3. μΈμ ‘ν•œ 정점을 λͺ¨λ‘ κ²€μ‚¬ν•˜κ³  λ‚˜λ©΄, μ§€κΈˆκΉŒμ§€ μ €μž₯ν•œ λͺ©λ‘μ—μ„œ λ‹€μŒ 정점을 κΊΌλ‚΄μ„œ λ°©λ¬Έ

λ„ˆλΉ„ μš°μ„  νƒμƒ‰μ˜ λ°©λ¬Έ μˆœμ„œλŠ” μ •μ μ˜ λͺ©λ‘μ—μ„œ μ–΄λ–€ 정점을 λ¨Όμ € κΊΌλ‚΄λŠ”μ§€μ— μ˜ν•΄ κ²°μ •

μœ„μ—μ„œ μ–ΈκΈ‰ν•œ β€œλ³„λ„μ˜ μœ„μΉ˜β€ λŠ” λ¨Όμ € λ“€μ–΄μ˜¨ 정점을 λ¨Όμ € κΊΌλ‚΄μ•Ό ν•˜λŠ” νŠΉμ„±μ„ κ°€μ Έμ•Ό ν•˜λ―€λ‘œ, Queue λ₯Ό μ‚¬μš©ν•˜μ—¬ ν•΄λ‹Ή 쑰건을 λ§Œμ‘±μ‹œν‚¨λ‹€.

깊이 μš°μ„  탐색과 달리 λ„ˆλΉ„ μš°μ„  νƒμƒ‰μ—μ„œλŠ” 발견과 방문이 κ°™μ§€ μ•Šλ‹€. λ”°λΌμ„œ λͺ¨λ“  정점은

  • 아직 λ°œκ²¬λ˜μ§€ μ•Šμ€ μƒνƒœ
  • λ°œκ²¬λ˜μ—ˆμ§€λ§Œ 아직 λ°©λ¬Έλ˜μ§€λŠ” μ•Šμ€ μƒνƒœ (Queue 에 μ €μž₯된 μƒνƒœ)
  • 방문된 μƒνƒœ 둜 3κ°€μ§€ μƒνƒœλ₯Ό κ°€μ§ˆ 수 μžˆλ‹€.

깊이 μš°μ„  νƒμƒ‰μ—μ„œμ²˜λŸΌ, μƒˆ 정점을 λ°œκ²¬ν•˜λŠ” 데 μ‚¬μš©ν–ˆλ˜ κ°„μ„ λ“€λ§Œμ„ λͺ¨μ€ 트리λ₯Ό λ„ˆλΉ„ μš°μ„  탐색 μŠ€νŒ¨λ‹ 트리(BFS Spanning Tree)라고 ν•œλ‹€.

πŸ’‘ μ‹œκ°„ λ³΅μž‘λ„

λͺ¨λ“  정점을 ν•œ λ²ˆμ”© λ°©λ¬Έν•˜λ©°, 정점을 λ°©λ¬Έν•  λ•Œλ§ˆλ‹€ μΈμ ‘ν•œ λͺ¨λ“  간선을 κ²€μ‚¬ν•˜κΈ° λ•Œλ¬Έμ—, 깊이 μš°μ„  탐색과 λ™μΌν•˜λ‹€.

πŸ’‘ λ„ˆλΉ„ μš°μ„  탐색과 μ΅œλ‹¨ 거리

κ·Έλž˜ν”„μ—μ„œμ˜ μ΅œλ‹¨ 경둜 문제λ₯Ό ν•΄κ²°ν•˜λŠ”λ° 주둜 μ‚¬μš©λœλ‹€.

λ„ˆλΉ„ μš°μ„  탐색 μ•Œκ³ λ¦¬μ¦˜μ„ κ°„λ‹¨ν•˜κ²Œ λ³€κ²½ν•΄ λͺ¨λ“  정점에 λŒ€ν•΄ μ‹œμž‘μ μœΌλ‘œλΆ€ν„°μ˜ 거리 distance[] λ₯Ό κ³„μ‚°ν•˜λ„λ‘ ν•  수 μžˆλ‹€.

  • 탐색 κ³Όμ •μ—μ„œ κ°„μ„  (u, v)λ₯Ό 톡해 정점 vλ₯Ό 처음 λ°œκ²¬ν•΄ Queue 에 λ„£λŠ”λ‹€κ³  κ°€μ •
  • μ‹œμž‘μ μœΌλ‘œλΆ€ν„° vκΉŒμ§€μ˜ μ΅œλ‹¨ 거리 distance[v] λŠ” μ‹œμž‘μ μœΌλ‘œλΆ€ν„° uκΉŒμ§€μ˜ μ΅œλ‹¨ 거리 distance[u] +1 μ΄λŠ” κ³§ μ‹œμž‘μ μœΌλ‘œλΆ€ν„° λ‹€λ₯Έ λͺ¨λ“  μ •μ κΉŒμ§€μ˜ μ΅œλ‹¨ 경둜λ₯Ό λ„ˆλΉ„ μš°μ„  탐색 μŠ€νŒ¨λ‹ 트리 (BFS Spanning Tree) μ—μ„œ 찾을 수 μžˆλ‹€λŠ” 것을 μ˜λ―Έν•œλ‹€.

πŸ’‘ μ–‘λ°©ν–₯ 탐색

두 정점 μ‚¬μ΄μ˜ μ΅œλ‹¨ 경둜λ₯Ό 찾을 λ•Œ μ‚¬μš©ν•  수 μžˆλŠ” ν…Œν¬λ‹‰ μ‹œμž‘ μ •μ μ—μ„œ μ‹œμž‘ν•˜λŠ” μ •λ°©ν–₯ 탐색과 λͺ©ν‘œ μ •μ μ—μ„œ μ‹œμž‘ν•΄ 거꾸둜 μ˜¬λΌμ˜€λŠ” μ—­λ°©ν–₯ 탐색을 λ™μ‹œμ— ν•˜λ©΄μ„œ, 이 λ‘˜μ΄ κ°€μš΄λ°μ„œ λ§Œλ‚˜λ©΄ μ’…λ£Œ

이λ₯Ό μ½”λ“œλ‘œ κ΅¬ν˜„ν•˜λ €λ©΄, μ •λ°©ν–₯κ³Ό μ—­λ°©ν–₯ νƒμƒ‰μ—μ„œ λ°©λ¬Έν•΄μ•Ό ν•  정점듀을 λͺ¨λ‘ 같은 Queue 에 μ €μž₯ν•˜λ˜, μ΅œλ‹¨ 거리λ₯Ό μ €μž₯ν•  λ•Œ μ •λ°©ν–₯은 μ–‘μˆ˜, μ—­λ°©ν–₯은 음수둜 μ €μž₯ν•œλ‹€. μΈμ ‘ν•œ μƒνƒœ 검사 μ‹œ, μ„œλ‘œ λΆ€ν˜Έκ°€ λ‹€λ₯΄λ‹€λ©΄ κ°€μš΄λ°μ„œ λ§Œλ‚¬μŒμ„ νŒŒμ•…ν•  수 μžˆλ‹€.

μ–‘λ°©ν–₯ 탐색은 λ„ˆλΉ„ μš°μ„  탐색보닀 훨씬 적은 μ •μ λ§Œμ„ λ°©λ¬Έν•˜κ³ λ„ μ΅œλ‹¨ 경둜λ₯Ό 찾을 수 μžˆμ–΄ λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ΄ 훨씬 적닀. ν•˜μ§€λ§Œ 이λ₯Ό μ‚¬μš©ν•  수 μ—†λŠ” κ²½μš°λ‚˜, λͺ©ν‘œ μ •μ κΉŒμ§€μ˜ μ΅œλ‹¨ 거리가 λ„ˆλ¬΄ μ»€μ„œ μ–‘λ°©ν–₯ νƒμƒ‰μœΌλ‘œλ„ μ΅œλ‹¨ 경둜λ₯Ό 찾을 수 μ—†λŠ” κ²½μš°λŠ” μ–΄λ–»κ²Œ ν•΄μ•Ό ν• κΉŒ?

πŸ’‘ 점점 κΉŠμ–΄μ§€λŠ” 탐색

= Iteratively Deepening Search = IDS

  • μž„μ˜μ˜ 깊이 μ œν•œ l을 μ •ν•œ ν›„ 이 μ œν•œλ³΄λ‹€ 짧은 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜λŠ”μ§€λ₯Ό 깊이 μš°μ„  νƒμƒ‰μœΌλ‘œ 확인
  • 닡을 찾으면 성곡, 이λ₯Ό λ°˜ν™˜
  • 닡을 μ°Ύμ§€ λͺ»ν•˜λ©΄ l을 λŠ˜λ €μ„œ λ‹€μ‹œ μ‹œλ„

μ΄λŠ” β€œμ‘°ν•© 탐색” κ³Ό 관련이 κΉŠλ‹€.

πŸ’‘ 탐색 방법 μ„ νƒν•˜κΈ°

  1. μƒνƒœ κ³΅κ°„μ—μ„œμ˜ μ΅œλ‹¨ 경둜λ₯Ό μ°ΎλŠ” 경우, λ„ˆλΉ„ μš°μ„  탐색을 μš°μ„ μ μœΌλ‘œ κ³ λ € (직관적이고 κ΅¬ν˜„λ„ 간단) νƒμƒ‰μ˜ 깊이 ν•œκ³„κ°€ μ •ν•΄μ Έ μžˆμ§€ μ•Šκ±°λ‚˜ λ„ˆλ¬΄ κΉŠμ–΄ λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ΄ λ„ˆλ¬΄ 크지 μ•Šμ€μ§€μ— λŒ€ν•œ 확인이 ν•„μš”
  2. μƒνƒœ κ³΅κ°„μ—μ„œμ˜ μ΅œλ‹¨ 경둜λ₯Ό μ°ΎλŠ”λ°, νƒμƒ‰μ˜ μ΅œλŒ€ κΉŠμ΄κ°€ μ •ν•΄μ Έ 있고 λ„ˆλΉ„ μš°μ„  탐색을 ν•˜κΈ°μ—λŠ” λ©”λͺ¨λ¦¬μ™€ μ‹œκ°„μ΄ λΆ€μ‘±ν•  경우, μ–‘λ°©ν–₯ 탐색을 κ³ λ € λͺ©ν‘œ μƒνƒœμ—μ„œ μ—­λ°©ν–₯으둜 움직이기가 쉬어야 ν•œλ‹€.
  3. 두 탐색이 λͺ¨λ‘ λ„ˆλ¬΄ λ©”λͺ¨λ¦¬λ₯Ό 많이 μ‚¬μš©ν•˜κ±°λ‚˜ λ„ˆλ¬΄ 느린 경우, μ΅œμ ν™”λ₯Ό ν•  거리가 더 λ§Žμ€ 점점 κΉŠμ–΄μ§€λŠ” 탐색을 μ‚¬μš©

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€